package cn.jolyoulu.common.core.algorithms.tree.biarysorttree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;

/**
 * @Author LuZhouJin
 * @Date 2022/6/24
 * 二叉排序树要求每个左节点必须小于父节点，每个右节点必须大于父节点，每个父节点下只有2个子节点
 */
@Slf4j
@Data
@AllArgsConstructor
@NoArgsConstructor
public class BinarySortTree<T extends Comparable<T>> {
    private Node<T> root;

    /**
     * 添加节点
     * @param node 节点
     */
    public void add(Node<T> node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder(c -> log.info(c.toString()));
        } else {
            throw new NullPointerException("二叉顺序树为空无法遍历");
        }
    }

    /**
     * 查找节点
     * @param value 节点内容
     * @return
     */
    public Node<T> search(T value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 查找父节点
     * @param value 节点内容
     * @return
     */
    public Node<T> searchParent(T value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 以传入node作为根节点循环向左节点查找删除并且返回最小节点的值
     * @param node 节点
     * @return 返回最小节点值
     */
    public T delRightTreeMin(Node<T> node) {
        Node<T> target = node;
        //一直向左边获取，直到最左叶子节点，即最小节点
        while (target.getLeft() != null) {
            target = target.getLeft();
        }
        //删除最小节点
        delNode(target.getValue());
        return target.getValue();
    }

    /***
     * 删除节点思路
     * 删除节点遇到3种情况
     * 1.删除叶子节点
     *      a.首先找到要删除的节点targetNode
     *      b.确定targetNode的父节点parent
     *      c.确定targetNode是paren的左子节点还是右子节点
     *      d.根据c确定情况设置parent.left=null/parent.right=null
     * 2.删除只有1个子树节点
     *      a.首先找到要删除的节点targetNode
     *      b.确定targetNode的父节点parent
     *      c.确定targetNode的子节点是左子节点还是右子节点
     *      d.targetNode是parent的左子节点还是右边子节点
     *        如果targetNode有左子节点: 1).targetNode是parent左子节点，parent.left=targetNode.left  ||  2).targetNode是parent右子节点，parent.right=targetNode.left
     *                                         parent                                          ||           parent
     *                                         /    \                                          ||           /    \
     *                                  targetNode  right                                      ||        right  targetNode
     *                                       /                                                 ||                /
     *                                   left                                                  ||             left
     *        如果targetNode有右子节点: 1).targetNode是parent左子节点，parent.left=targetNode.right ||   2).targetNode是parent右子节点，parent.right=targetNode.right
     *                                         parent                                          ||            parent
     *                                         /    \                                          ||            /    \
     *                                  targetNode  right                                      ||        right  targetNode
     *                                       \                                                 ||                  \
     *                                       right                                             ||                  right
     * 3.删除有2个子树的节点
     *      a.首先找到要删除的节点targetNode
     *      b.确定targetNode的父节点parent
     *      c.从targetNode右子树找到最小节点(如果从左子树找那么就找到最大节点)
     *      d.用临时变量，将最小节点的值保存到temp中
     *      e.删除最小节点
     *      f.targetNode.value = temp
     */
    public void delNode(T value) {
        if (root == null) {
            return;
        } else {
            //先去查找要删除的节点
            Node<T> targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            //targetNode已经是最后一个节点直接删除
            if (root.getLeft() == null && root.getRight() == null) {
                root = null;
                return;
            }
            //查找父节点
            Node<T> parent = searchParent(value);
            //如果删除的节点是叶子节点
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                //如果targetNode是parent的左子节点
                if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
                    parent.setLeft(null);
                    //如果targetNode是parent的右子节点
                } else if (parent.getRight() != null && parent.getRight().getValue() == value) {
                    parent.setRight(null);
                }
                //如果是有2个子树的节点
            } else if (targetNode.getLeft() != null && targetNode.getRight() != null) {
                //已当前节点右子节点为根节点，找到最小值
                T min = delRightTreeMin(targetNode.getRight());
                targetNode.setValue(min);
                //如果只有1个子树的节点
            } else {
                //如果targetNode只有左子节点
                if (targetNode.getLeft() != null) {
                    if (parent != null) {
                        //如果targetNode是parent的左子节点
                        if (parent.getLeft().getValue().compareTo(value) == 0) {
                            parent.setLeft(targetNode.getLeft());
                            //如果targetNode是parent的右子节点
                        } else {
                            parent.setRight(targetNode.getLeft());
                        }
                        //当前节点没有父节点，那么表示该节点是root节点
                    } else {
                        root = targetNode.getLeft();
                    }
                    //如果targetNode只有右子节点
                } else {
                    if (parent != null) {
                        //如果targetNode是parent的左子节点
                        if (parent.getLeft().getValue().compareTo(value) == 0) {
                            parent.setLeft(targetNode.getRight());
                            //如果targetNode是parent的右子节点
                        } else {
                            parent.setRight(targetNode.getRight());
                        }
                        //当前节点没有父节点，那么表示该节点是root节点
                    } else {
                        root = targetNode.getRight();
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        BinarySortTree<Integer> tree = new BinarySortTree<>();
        int[] arr = {7,3,10,12,5,1,9,2};
        System.out.println("=====================添加数据=====================");
        for (int i : arr){
            tree.add(new Node<>(i));
        }
        tree.infixOrder();
        System.out.println("=====================删除叶子节点=====================");
        tree.delNode(2);
        tree.infixOrder();
        System.out.println("=====================删除1个子树叶子节点=====================");
        tree.add(new Node<>(2));
        tree.delNode(1);
        tree.infixOrder();
        System.out.println("=====================删除2个子树叶子节点=====================");
        tree.delNode(10);
        tree.infixOrder();
    }
}
